/*
 * matching.h
 *
 *  Created on: Apr 28, 2011
 *      Author: tqlong
 */

#ifndef MATCHING_H_
#define MATCHING_H_
#include <queue>
#include <set>
#include "kdtree.h"

class Matching {
public:
  //typedef std::vector<vec> dataset_type;
private:
  std::vector<double> m_dist;
  std::vector<int> m_pred;
  int m_cycleStart;
protected:
  const dataset_type &m_set1, &m_set2;
  std::vector<int> m_matchIdx;
public:
  Matching(const dataset_type & set1, const dataset_type &set2);
  virtual ~Matching() {}

  double weight(int i, int j) const;

  int n() const;

  int match(int i) const;

  double cost(const std::vector<int>& matchIdx);

  double cost();

  virtual void doMatch();

  bool findNegativeCycle();

  void updateCycle();

  void outputDistances() const;
};

class KDTreePrice: public KDTree {
protected:
  typedef KDTree __Base;
  //typedef __Base ::dataset_type dataset_type;

  double m_minPrice;
  std::vector<double>& m_price;
public:
  KDTreePrice(const dataset_type& data, std::vector<double>& price);

  KDTreePrice(KDTreePrice* parent, int s, int e);

  Tree* createChild(int s, int e);

  KDTreePrice* child(int i);

  KDTreePrice* parent();

  double findKNN(const vec& query, std::vector<int>& knnIdx,
      std::vector<double>& minBound);

  double price(int idx) const;

  void updateMinPrice(int idx);

  KDTreePrice* findLeaf(int idx);

  void updateMinPrice();

  void resetPrice();
};

class AuctionMatching: public Matching {
protected:
  std::vector<double> m_price;
  int m_count;
  std::vector<std::vector<int> > m_bestIdx;
  std::vector<double> m_thirdY;
public:
  typedef Matching              __Base;
  //typedef __Base::dataset_type  dataset_type;
public:
  AuctionMatching(const dataset_type & set1, const dataset_type &set2);

  void doMatch();

  void findBest(int i, double& v, double& w, int& min_j);

  bool canPruned(int i, double& v, double& w, int& min_j);
}; // AuctionMatching

class AuctionMatchingKDTree: public AuctionMatching {
  KDTreePrice *m_tree;
  double m_pruned;
public:
  typedef AuctionMatching     __Base;
  //typedef __Base::dataset_type  dataset_type;
public:
  AuctionMatchingKDTree(const dataset_type & set1,
      const dataset_type &set2);

  ~AuctionMatchingKDTree();

  void doMatch();

  void findBest(int i, double& v, double& w, int& min_j);

  bool canPruned(int i, double& v, double& w, int& min_j);
};

class MaximumMatching : public Matching
{
protected:
  double m_r;
  KDTree* m_tree;
  std::vector<int> m_prev;
  std::queue<int> m_queue;
  int m_Y, m_count;
  struct NeighborHood {
    MaximumMatching& m_matcher;
    const vec& m_v;
    double m_r;
    bool m_findAll;
    bool m_found;
    std::vector<int> m_nearIdx;
    NeighborHood(MaximumMatching& matcher, const vec& v, double r, bool findAll) :
      m_matcher(matcher), m_v(v), m_r(r), m_findAll(findAll), m_found(false) {}

    bool isFindAll() const { return m_findAll; }
    bool isFound() const { return m_found; }
    bool set_found(bool found) { m_found = found; }
    bool ok(const BoundingBox& b) { return b.lowerBound(m_v) <= m_r; }
    bool ok(KDTree* node, int i)
    {
      return arma::norm(m_v-node->get(i), 2) <= m_r &&
             m_matcher.m_matchIdx[node->originalIdx(i)+m_matcher.n()] == -1;
    }
    void process(KDTree* node, int i) { m_nearIdx.push_back(node->rootIdx(i)); }
  };
  struct NeighborHood1 : public NeighborHood {
    int m_i;

    NeighborHood1(MaximumMatching& matcher, int i, double r, bool findAll) :
      NeighborHood(matcher, matcher.m_set1[i], r, findAll), m_i(i) {}

    bool ok(const BoundingBox& b) { return b.lowerBound(m_v) <= m_r; }
    bool ok(KDTree* node, int i)
    {
      return arma::norm(m_v-node->get(i), 2) <= m_r;
    }
    void process(KDTree* node, int j_idx);
  };
public:
  MaximumMatching(const dataset_type & set1, const dataset_type &set2, double r);

  ~MaximumMatching();

  void doMatch();
};

class StableMatching : public MaximumMatching
{
  struct nb_dist {
    int idx;
    double dist;
  };
  struct nb_less {
    bool operator()(const nb_dist& a, const nb_dist& b) const { return a.dist < b.dist; }
  };
  std::vector<std::vector<nb_dist> > m_neighbors;
public:
  StableMatching(const dataset_type & set1, const dataset_type &set2, double r);
  void doMatch();
  void computeNeigbors;
};

#endif /* MATCHING_H_ */
